#include "BinarySearchTree.h"

void TestBSTree1() 
{
	BSTree<int> t;
	int arr[] = { 8, 3, 1, 10, 2, 2, 3, 6, 4, 7, 14, 13 };
	for (const auto& e : arr)
	{
		t.Insert(e);
	}
	t.InOrder();

	t.Erase(8);
	t.Erase(3);
	t.InOrder();
	for (const auto& e : arr)
	{
		t.Erase(e);
	}
	t.InOrder();
}

void TestBSTree2()
{
	BSTree<int> t;
	int arr[] = { 8, 3, 1, 10, 2, 2, 3, 6, 4, 7, 14, 13 };
	for (const auto& e : arr)
	{
		t.InsertR(e);
	}
	t.InOrder();

	t.EraseR(8);
	t.EraseR(3);
	t.EraseR(2);
	t.InOrder();
	cout << t.Find(10) << endl;
	cout << t.Find(100) << endl;
	cout << t.FindR(10) << endl;
	cout << t.FindR(100) << endl;
	for (const auto& e : arr)
	{
		t.EraseR(e);
	}
	t.InOrder();
}

void TestBSTree3()
{
	BSTree<int> t;
	int arr[] = { 8, 3, 1, 10, 2, 2, 3, 6, 4, 7, 14, 13 };
	for (const auto& e : arr)
	{
		t.InsertR(e);
	}
	t.InOrder();

	BSTree<int> copy = t;
	copy.InOrder();

	BSTree<int> t2;
	t2.Insert(3);
	t2.Insert(5);
	t2.Insert(4);
	copy = t2;
	t2.InOrder();
	copy.InOrder();
}

int main()
{
	//TestBSTree3();
	KeyValue::TestBSTree2();

	//vector<int> v1 = { 9, 3, 15, 20, 7 };
	//vector<int> v2 = { 9, 15, 7, 20, 3 };
	//Solution s;
	//s.buildTree(v1, v2);

	return 0;
}

//#include <queue>
//class MyStack {
//public:
//	queue<int> q1;
//	queue<int> q2;
//
//	/** Initialize your data structure here. */
//	MyStack() {
//
//	}
//
//	/** Push element x onto stack. */
//	void push(int x) {
//		q2.push(x); // q2入队列
//		while (!q1.empty()) // 把q1的元素全入到q2
//		{
//			q2.push(q1.front());
//			q1.pop();
//		}
//		swap(q1, q2); // 交换q1和q2 1.如nullptr和1
//	}
//
//	/** Removes the element on top of the stack and returns that element. */
//	int pop() {
//		int r = q1.front();
//		q1.pop();
//		return r;
//	}
//
//	/** Get the top element. */
//	int top() {
//		int r = q1.front();
//		return r;
//	}
//
//	/** Returns whether the stack is empty. */
//	bool empty() {
//		return q1.empty();
//	}
//};
//
//class Solution {
//public:    // 这里的2有人当成to命名
//	string tree2str(TreeNode* root) {
//		if (root == nullptr)
//		{
//			return string(); // 返回匿名对象
//		}
//		string str;
//		str += to_string(root->val);
//
//		if (root->left || root->right)//左不为空或者左为空,右不为空,左需要加括号
//		{
//			str += '(';
//			str += tree2str(root->left);
//			str += ')';
//		}
//
//		if (root->right)//右不为空,右需要加括号
//		{
//			str += '(';
//			str += tree2str(root->right);
//			str += ')';
//		}
//		return str;
//	}
//};
//
//int PartSort(int* arr, int left, int right)
//{
//	int keyi = left;
//	int prev = left;
//	int cur = left + 1;
//	while (cur <= right)
//	{
//		if (arr[cur] < arr[keyi] && ++prev != cur)
//		{
//			swap(arr[cur], arr[prev]);
//		}
//		++cur;
//	}
//	swap(arr[prev], arr[keyi]);
//	return prev;
//}
//
//void QuickSort(int* arr, int left, int right)
//{
//	if (left >= right)
//	{
//		return;
//	}
//	int keyi = PartSort(arr, left, right);
//	QuickSort(arr, left, keyi - 1);
//	QuickSort(arr, keyi + 1, right);
//}
//
//
//int main()
//{
//	int arr[] = { 3,2,1,6,5,4,9,8,7,0 };
//	QuickSort(arr, 0, 9);
//	for (const auto& e : arr)
//	{
//		cout << e << " ";
//	}
//	cout << endl;
//	return 0;
//}